Решение: прибавление арифметической прогрессии по диагоналям, вертикали и горизонтали в офлайне, получим решение за $$$O(nm)$$$.